"""
2411. 按位或最大的最小子数组长度
中等
相关标签
premium lock icon
相关企业
提示
给你一个长度为 n 下标从 0 开始的数组 nums ，数组中所有数字均为非负整数。对于 0 到 n - 1 之间的每一个下标 i ，你需要找出 nums 中一个 最小 非空子数组，它的起始位置为 i （包含这个位置），同时有 最大 的 按位或运算值 。

换言之，令 Bij 表示子数组 nums[i...j] 的按位或运算的结果，你需要找到一个起始位置为 i 的最小子数组，这个子数组的按位或运算的结果等于 max(Bik) ，其中 i <= k <= n - 1 。
一个数组的按位或运算值是这个数组里所有数字按位或运算的结果。

请你返回一个大小为 n 的整数数组 answer，其中 answer[i]是开始位置为 i ，按位或运算结果最大，且 最短 子数组的长度。

子数组 是数组里一段连续非空元素组成的序列。



示例 1：

输入：nums = [1,0,2,1,3]
输出：[3,3,2,2,1]
解释：
任何位置开始，最大按位或运算的结果都是 3 。
- 下标 0 处，能得到结果 3 的最短子数组是 [1,0,2] 。
- 下标 1 处，能得到结果 3 的最短子数组是 [0,2,1] 。
- 下标 2 处，能得到结果 3 的最短子数组是 [2,1] 。
- 下标 3 处，能得到结果 3 的最短子数组是 [1,3] 。
- 下标 4 处，能得到结果 3 的最短子数组是 [3] 。
所以我们返回 [3,3,2,2,1] 。
示例 2：

输入：nums = [1,2]
输出：[2,1]
解释：
下标 0 处，能得到最大按位或运算值的最短子数组长度为 2 。
下标 1 处，能得到最大按位或运算值的最短子数组长度为 1 。
所以我们返回 [2,1] 。


提示：

n == nums.length
1 <= n <= 105
0 <= nums[i] <= 109
"""
from typing import List


class Solution:
    def smallestSubarrays(self, nums: List[int]) -> List[int]:
        """
        两层遍历，第一层遍历i:[0,n),第二从后往前[i-1,0],每次都或上当前元素nums[i]
        简单来说每个nums都存储以当前为起始的子集，而每次遍历i都是完成[当前节点,i]的集合
          [1,0,2,1,3]
        1 [1,x,x,x,x] i=1,[0,1)元素|1
        2 [1,0,x,x,x] i=2,[0,2)元素|0
        3 [3,2,2,x,x] i=3,[0,3)元素|2
        4 [3,3,3,1,3] i=4,[0,4)元素|1
        5 [3,3,3,3,3] i=5,[0,5)元素|3
        已知遍历过程中后面是前面的子集（dp[i]<dp[j]时，dp[j]∈dp[i],因为dp[i]多或了nums[i,j)），若新遍历的二进制是右边的子集，则他必定也是左边的子集
        :param nums:
        :return:
        """
        #结果
        dp = [1] * len(nums)
        for i,j in enumerate(nums):
            for k in range(i-1,-1,-1):
                if nums[k]|j == nums[k]:
                    # 无效子集，前面是j的父级更加不可能增加，直接跳过
                    break
                #不是子集说明数字有添加，更新结果
                nums[k] = nums[k]|j
                dp[k] = i - k + 1
        return dp
    def smallestSubarrays_res1(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        left_or = suf_or = 0
        right = bottom = n - 1
        for left in range(n - 1, -1, -1):
            suf_or |= nums[left]
            left_or |= nums[left]
            while right >= left and (left_or | nums[right]) == suf_or:
                right -= 1
                # 栈为空
                if bottom > right:
                    # 重新构建一个栈，栈底为 left，栈顶为 right
                    for i in range(left + 1, right + 1):
                        nums[i] |= nums[i - 1]
                    bottom = left
                    left_or = 0
            # 循环结束后 [left,right] 不满足要求，但 [left,right+1] 满足要求
            ans[left] = right - left + 2
        return ans

if __name__ == '__main__':
    a = "http://localhost/dev-api/scamp/scampVehicle/list?pageNum=1&pageSize=10&params%5BselectedOrgIds%5D=60cf2226-b121-11ef-b39d-008cfaf2b915%2C1ea1354e-f726-43fa-b2bb-6252484b75e5%2Ca437b85e-c67f-4dad-bd42-66ad41809319%2C63b83763-8212-4296-a65b-a006b8c0860e%2Cfe895be4-b07f-413a-b5e6-29da4bf52f83%2C2e52ddcf-d833-415a-838f-5beb01815bc7%2C300e9dd1-6cae-468a-8b28-b22103f1c928%2Cc850f47e-5820-47fc-9fd6-06302dd9fa37%2C61e53416-fdad-48da-b22e-b41ae768e9bf%2C0b83fbb0-982b-488f-af83-056b79e50a99%2C651c203c-0e9b-428f-96ec-efcc6c624a18%2Cf77e7e3c-782b-42fe-a54c-a4ccfad85248%2C478354e2-0ffe-4241-9bd1-90c9b4e4ea53%2Cf935cc6d-4e4a-4e33-9e16-856775a84bbe%2C9e0a02dc-eb21-45e6-b7d8-f3db323bbb2a%2Cdd2cb950-78c7-4122-a90e-2f9130fb68fd%2C3ccf652b-219f-4c6d-a2de-5d5ee122276d%2C144bc5f6-83aa-4f1c-a3df-46381a98b7e8%2C4389cb86-4451-4df9-9285-775c0936925b%2C9ac6d084-b06c-41ea-81a1-90a270c6a909%2C3b263567-22c6-4d92-a058-3268043eea22%2Cbaff797f-0b78-4bb9-b27e-7bcf9587bf5a%2C044656d3-8374-49e8-a219-82fcb1232b30%2C3e0f6bdd-8fc7-4d15-9575-f5c1d2193254%2Cdec8090d-2aab-4754-843a-9e417f8a7c57%2Cce45ceec-7388-4513-99c3-df236e3cde49%2Cacef8576-b408-4b80-8322-21e1fb6ad1fa%2C4ef4a556-7147-448c-a655-07b5b2675ce1%2C2b6d9a0f-a88e-47f4-84da-728d3e557974%2Cae08890c-51ca-4fec-ad27-9e85cb25e2d6%2Cdc241afc-9bf3-4043-bdd2-7f0de26fe9cf&vehicleType=0"
    print(len(a))
    # print(Solution().smallestSubarrays([1,0,2,1,3]))
    print(Solution().smallestSubarrays_res1([1,0,2,1,3]))